"""
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：

输入：nums = [3,2,4], target = 6 输出：[1,2]
示例 3：

输入：nums = [3,3], target = 6 输出：[0,1]

提示：

2 <= nums.length <= 104 -109 <= nums[i] <= 109 -109 <= target <= 109 只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？
"""
import time

# nums = [3, 3]
nums = [3, 2, 4]
target = 6
# nums = [2, 7, 11, 15]
# target = 9
# start = time.time()
# time.sleep(1)
# for i in range(len(nums)):
#     for j in range(len(nums)):
#         if i == j:
#             continue
#         if nums[i] + nums[j] == target:
#             print([i, j])
#             break
# end = time.time()
# print(f"运行时间:{end-start}")
# 优化后 --> O(n)
start = time.time()
time.sleep(1)
nums_dict = {}  # 用字典存储已经遍历过的索引和值
for i, num in enumerate(nums):  # 遍历取索引和值
    nums_dict = {i: num}  # 存于字典
    if target - nums_dict[i] in nums and nums.index(target-nums_dict[i]) != i:
        # 判断 target减去当前元素后的值是否在nums中，且这个值的索引不等于当前元素的索引
        print([i, nums.index(target - num)])  # 返回两个值的索引
        break  # 找到就结束循环
end = time.time()
print(f"运行时间:{end-start}")


# 0.0000433921813965

# 0.0015075206756592
